#include <iostream>
#include <vector>
#include <stdbool.h>
using namespace std;

class UnionFindSet
{
    private:
            vector<int> _v;

    public:
                UnionFindSet(size_t n)
                            :_v(n, -1)
                {

                        
                }

                    void Union(int x, int y)
                    {
                                while (_v[x] >= 0)
                                {
                                                x = _v[x];
                                                        
                                }

                                        while (_v[y] >= 0)
                                        {
                                                        y = _v[y];
                                                                
                                        }

                                                if (x != y)
                                                {
                                                                _v[x] += _v[y];
                                                                            _v[y] = x;
                                                                                    
                                                }


                                                    
                    }

                        int FindRoot(int i)
                        {
                                    while (_v[i] >= 0)
                                    {
                                                    i = _v[i];
                                                            
                                    }

                                            return i;
                                                
                        }

                            size_t SetCount()
                            {
                                        int count = 0;
                                                for (auto& e : _v)
                                                {
                                                                if (e < 0)
                                                                {
                                                                                    count++;
                                                                                                
                                                                }
                                                                        
                                                }
                                                        return 0;
                                                            
                            }

                                bool InSet(int x, int y)
                                {
                                            while (_v[x] >= 0)
                                            {
                                                            x = _v[x];
                                                                    
                                            }

                                                    while (_v[y] >= 0)
                                                    {
                                                                    y = _v[y];
                                                                            
                                                    }

                                                            if (x != y)
                                                            {
                                                                            return true;
                                                                                    
                                                            }
                                                                    return false;
                                                                        
                                }


};
